package Leetcode;

import base.TreeNode;

import java.util.*;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * 输入: [1,2,3,null,5,null,7]
 * 输出: [1,3,7]
 */
public class 力扣199_二叉树的右视图 {
    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode e = new TreeNode(5);
        TreeNode g = new TreeNode(7);
        a.left = b;
        a.right = c;
        b.right = e;
        c.right = g;
        List<Integer> integers = rightSideView2(a);
        System.out.println(integers);

        // 当输入为数组的时候
        int[] array = {1, 2, 3, -1, 5, -1, 4};
        int[] list = new int[array.length];
        dfs(array, 0, 0, list);
        for (int num : list) {
            System.out.print(num);
        }
    }

    // 1 通过层级遍历 获取数组第一个数字返回列表
    static List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<List<Integer>> lists = getLevelOrderList(root);
        for (List<Integer> list : lists) {
            result.add(list.get(0));
        }
        return result;
    }

    static List<List<Integer>> getLevelOrderList(TreeNode root) {
        List<List<Integer>> rs = new ArrayList<>();
        levelOrder(rs, root, 0);
        return rs;
    }

    static void levelOrder(List<List<Integer>> rs, TreeNode node, Integer level) {
        List<Integer> list = null;
        if (rs.size() < level + 1) {
            list = new ArrayList<>();
            rs.add(level, list);
        } else {
            list = rs.get(level);
        }
        list.add(node.val);
        if (node.right != null) {
            levelOrder(rs, node.right, level + 1);
        }
        if (node.left != null) {
            levelOrder(rs, node.left, level + 1);
        }
    }

    // 2 通过深度优先遍历 更新每层的数据
    static List<Integer> rightSideView2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Map<Integer, Integer> everyLayerValueAtDepth = new HashMap<>();
        Queue<TreeNode> nodeQueue = new ArrayDeque<>();
        Queue<Integer> depthQueue = new ArrayDeque<>();
        nodeQueue.add(root);
        depthQueue.add(0);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
            Integer depth = depthQueue.remove();
            everyLayerValueAtDepth.put(depth, node.val);
            if (node.left != null) {
                nodeQueue.add(node.left);
                depthQueue.add(depth + 1);
            }
            if (node.right != null) {
                nodeQueue.add(node.right);
                depthQueue.add(depth + 1);
            }
        }
        for (int i = 0; i < everyLayerValueAtDepth.size(); i++) {
            result.add(everyLayerValueAtDepth.get(i));
        }
        return result;
    }


    static void dfs(int[] array, int index, int level, int[] list) {
        if (index > array.length) {
            return;
        }
        int num = array[index];
        if (num == -1) {
            return;
        }
        // 因为每层是从左到右，所以遇到数据就先更新，也可以从右到左，但是要改为没有数据才更新
        list[level] = num;
        // 二叉树的左节点
        int left = index * 2 + 1;
        // 二叉树的右节点
        int right = index * 2 + 2;
        dfs(array, left, level + 1, list);
        dfs(array, right, level + 1, list);
    }


}
